class Solution {
public:
    string getPermutation(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      vector<int> p(n + 1);
      string s;
      string result;

      p[0] = 1;
      for (int i = 1; i <= n; ++i) {
        p[i] = i * p[i - 1];
        s += static_cast<char>(i + '0');
      }
      GetPermutation(s, k, p, result);
      return result;
    }

    void GetPermutation(const string& s, int k, const vector<int>& p, string& result) {
      if (k <= 1) {
        result += s;
        return;
      }

      int sum = 0;
      int pos = 0;
      int n = s.length();

      for (; pos < n; ++pos) {
        if (sum + p[n - 1] >= k) {
          break;
        }
        sum += p[n - 1];
      }

      result += s[pos];
      GetPermutation(s.substr(0, pos) + s.substr(pos + 1), k - sum, p, result);
    }
};
